package io.adrainty.algorithm.leetcode.normal;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 2327. 知道秘密的人数
 * @author AdRainty
 * @version V1.0.0
 * @since 2025/9/9 下午9:09
 */
public class Solution2327 {

    public int peopleAwareOfSecret(int n, int delay, int forget) {
        final int MOD = 1000000007;
        // dp[i] 表示在第 i 天新知道秘密的人数
        long[] dp = new long[n + 1];
        dp[1] = 1; // 第一天有一个人知道秘密

        // 计算每一天新知道秘密的人数
        for (int i = 1 + delay; i <= n; i++) {
            // 在第 i 天分享秘密的人是那些在 [i-forget+1, i-delay] 天内知道秘密的人
            for (int j = Math.max(1, i - forget + 1); j <= i - delay; j++) {
                dp[i] = (dp[i] + dp[j]) % MOD;
            }
        }

        // 统计第 n 天仍然知道秘密的人数
        long result = 0;
        for (int i = Math.max(1, n - forget + 1); i <= n; i++) {
            result = (result + dp[i]) % MOD;
        }

        return (int) result;
    }

    @SuppressWarnings("all")
    public int peopleAwareOfSecret1(int n, int delay, int forget) {
        final int MOD = 1000000007;

        // 队列中存储每个人的两个状态：[已存在天数, 总存活天数]
        Queue<int[]> queue = new LinkedList<>();
        // 初始状态：第1天有1个人知道秘密，已存在1天，总共可以存活forget天
        queue.add(new int[]{1, forget});

        for (int day = 1; day < n; day++) {
            int size = queue.size();
            int newPeople = 0;

            for (int j = 0; j < size; j++) {
                int[] person = queue.poll();
                int existDays = person[0]; // 已存在的天数
                int totalDays = person[1]; // 总共能存活的天数

                // 如果这个人已经忘记了秘密，则不再计入统计
                if (existDays >= totalDays) continue;

                // 如果可以分享秘密（已存在天数>=delay），则新增一个人知道秘密
                if (existDays >= delay) {
                    newPeople++;
                }

                // 更新当前人的状态：已存在天数加1
                queue.add(new int[]{existDays + 1, totalDays});
            }

            // 将新知道秘密的人加入队列
            for (int i = 0; i < newPeople; i++) {
                queue.add(new int[]{1, forget});
            }
        }

        return queue.size() % MOD;
    }

}
